package com.xq.algorithm.sort;

import static com.xq.algorithm.AlgorithmTest.printlnAry;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/09.
 *         选择排序
 */

public class SelectSortAlgorithm {

    /**
     * 直接选择排序
     * 不稳定排序
     * @param a
     * 简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。 　　
     * 当i=1时，需进行n-1次比较；
     * 当i=2时，需进行n-2次比较；
     * 依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，
     * 即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。
     */
    public static void selectSort(int[] a){
        if(a == null) return;
        int n = a.length;
        int small,temp;
        for(int i=0; i < n-1;i++){
            small = i;
            for(int j= i +1; j < n; j++){
                if(a[j] < a[small]){
                    small = j;
                }
            }

            if(small != i){
                temp = a[small];
                a[small] = a[i];
                a[i] = temp;
            }
        }
    }

    public static void testSelectSort(){
        int[] a = new int[]{64,5,7,89,6,24};
        printlnAry(a);
        selectSort(a);
        printlnAry(a);
    }

    /**
     * 创建最大堆
     * @param a
     * @param n 二叉树的最后一个节点的索引
     * @param h 二叉树根节点索引
     */
    public static void  creatHeap(int[] a,int n, int h){
        int i,j,temp;
        boolean flag = false;
        i = h; //二叉树的根节点索引
        j = 2 * i + 1; //二叉树的左孩子节点的索引
        temp = a[i];
        while(j < n && !flag){
            if(j < n - 1 && a[j] < a[j+1]) j++; //左右孩子节点先比较选出一个最大值的索引
            if(temp > a[j]){
                flag = true;
            }else {
                a[i] = a[j];
                i = j;  //继续从交换后的孩子节点为新的父节点往下调整
                j = 2 * i + 1;
            }
        }
        a[i] = temp;
    }

    /**
     * 初始化最大堆
     * @param a
     */
    public static void initCreatHeap(int[] a){
        if(a == null)return;
        int n = a.length -1;
        for(int i = (n - 1) / 2; i >=0; i--){
            creatHeap(a,n,i);
        }
    }

    /**
     * 堆排序
     * @param a
     * 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。
     * 可以利用数组的特点快速定位指定索引的元素。堆分为最大堆和最小堆，是完全二叉树。
     * 最大的要求是每个节点的值都不大于其父节点的值。
     * 由于堆中每次都只能删除第0个数据，通过　取出第０个数据再执行堆的删除操作、重建堆
     * （实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。），
     * 然后再取，如此重复实现排序。
     */
    public static void headSort(int a[]){
         initCreatHeap(a); //初始化最大堆
        for(int i = a.length - 1; i > 0; i--){
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            creatHeap(a,i,0); //从堆的顶部再次调整堆
        }

    }


    public static void testHeadSort(){
        int[] a = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
        printlnAry(a);
        headSort(a);
        printlnAry(a);
    }
}
